home *** CD-ROM | disk | FTP | other *** search
/ EnigmA Amiga Run 1996 June / EnigmA AMIGA RUN 08 (1996)(G.R. Edizioni)(IT)[!][issue 1996-06][EARSAN CD VII].iso / earcd / gcc / ixemlsrc.lha / ixemul / ixnet / hash.h < prev    next >
C/C++ Source or Header  |  1996-03-13  |  10KB  |  286 lines
  1. #ifndef _HASH_H_
  2. #define _HASH_H_
  3.  
  4. /*-
  5.  * Copyright (c) 1990 The Regents of the University of California.
  6.  * All rights reserved.
  7.  *
  8.  * This code is derived from software contributed to Berkeley by
  9.  * Margo Seltzer.
  10.  *
  11.  * Redistribution and use in source and binary forms, with or without
  12.  * modification, are permitted provided that the following conditions
  13.  * are met:
  14.  * 1. Redistributions of source code must retain the above copyright
  15.  *    notice, this list of conditions and the following disclaimer.
  16.  * 2. Redistributions in binary form must reproduce the above copyright
  17.  *    notice, this list of conditions and the following disclaimer in the
  18.  *    documentation and/or other materials provided with the distribution.
  19.  * 3. All advertising materials mentioning features or use of this software
  20.  *    must display the following acknowledgement:
  21.  *    This product includes software developed by the University of
  22.  *    California, Berkeley and its contributors.
  23.  * 4. Neither the name of the University nor the names of its contributors
  24.  *    may be used to endorse or promote products derived from this software
  25.  *    without specific prior written permission.
  26.  *
  27.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  28.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  31.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37.  * SUCH DAMAGE.
  38.  *
  39.  *    @(#)hash.h      5.4 (Berkeley) 3/12/91
  40.  */
  41.  
  42. /* Operations */
  43. typedef enum { HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE,
  44.         HASH_FIRST, HASH_NEXT } HASH_ACTION;
  45.  
  46. /* Buffer Management structures */
  47. typedef struct _bufhead BUFHEAD;
  48.  
  49. struct _bufhead {
  50.     BUFHEAD    *prev;        /* LRU links */
  51.     BUFHEAD    *next;        /* LRU links */
  52.     BUFHEAD    *ovfl;        /* Overflow page buffer header */
  53.     u_int     addr;        /* Address of this page */
  54.     char    *page;        /* Actual page data */
  55.     char    flags;
  56. #define BUF_MOD     0x0001
  57. #define BUF_DISK    0x0002
  58. #define BUF_BUCKET    0x0004
  59. #define BUF_PIN     0x0008
  60. };
  61.  
  62.  
  63. #define IS_BUCKET(X)    (X & BUF_BUCKET)
  64.  
  65. typedef BUFHEAD **SEGMENT;
  66.  
  67. /* Hash Table Information */
  68. typedef struct hashhdr {    /* Disk resident portion */
  69.     int magic;    /* Magic NO for hash tables */
  70.     int version;    /* Version ID */
  71.     long lorder;    /* Byte Order */
  72.     int bsize;    /* Bucket/Page Size */
  73.     int bshift;    /* Bucket shift */
  74.     int dsize;    /* Directory Size */
  75.     int ssize;    /* Segment Size */
  76.     int sshift;    /* Segment shift */
  77.     int max_bucket; /* ID of Maximum bucket in use */
  78.     int high_mask;    /* Mask to modulo into entire table */
  79.     int low_mask;    /* Mask to modulo into lower half of table */
  80.     int ffactor;    /* Fill factor */
  81.     int nkeys;    /* Number of keys in hash table */
  82.     int hdrpages;    /* Size of table header */
  83.     int h_charkey;    /* value of hash(CHARKEY) */
  84. # define NCACHED        32    /* number of bit maps and spare points*/
  85.     int spares[NCACHED];    /* spare pages for overflow */
  86.     u_short bitmaps[NCACHED];    /* address of overflow page bitmaps */
  87. } HASHHDR;
  88.  
  89. typedef struct htab {    /* Memory resident data structure */
  90.     HASHHDR hdr;    /* Header */
  91.     int nsegs;    /* Number of allocated segments */
  92.     int exsegs;    /* Number of extra allocated segments */
  93.     int (*hash)();  /* Hash Function */
  94.     int flags;    /* Flag values */
  95.     int fp;     /* File pointer */
  96.     char *tmp_buf;    /* Temporary Buffer for BIG data */
  97.     char *tmp_key;    /* Temporary Buffer for BIG keys */
  98.     BUFHEAD *cpage; /* Current page */
  99.     int cbucket;    /* Current bucket */
  100.     int cndx;    /* Index of next item on cpage */
  101.     int tab_errno;    /* Error Number -- for DBM compatability */
  102.     int new_file;    /* Indicates whether fd is backing store or no */
  103.     int save_file;    /* Indicates whether we need to flush file at exit */
  104.     u_long *mapp[NCACHED];    /* Pointers to page maps */
  105.     int nmaps;    /* Initial number of bitmaps */
  106.     int nbufs;    /* Number of buffers left to allocate */
  107.     BUFHEAD bufhead; /* Header of buffer lru list */
  108.     SEGMENT  *dir;    /* Hash Bucket directory */
  109. } HTAB;
  110.  
  111.  
  112. /*
  113.  * Constants
  114.  */
  115. #define MAX_BSIZE        65536    /* 2^16 */
  116. #define MIN_BUFFERS        6
  117. #define MINHDRSIZE        512
  118. #define DEF_BUFSIZE        65536    /* 64 K */
  119. #define DEF_BUCKET_SIZE 256
  120. #define DEF_BUCKET_SHIFT    8    /* log2(BUCKET) */
  121. #define DEF_SEGSIZE        256
  122. #define DEF_SEGSIZE_SHIFT        8      /* log2(SEGSIZE)  */
  123. #define DEF_DIRSIZE        256
  124. #define DEF_FFACTOR        5
  125. #define SPLTMAX     8
  126. #define CHARKEY     "%$sniglet^&"
  127. #define NUMKEY            1038583
  128. #define VERSION_NO        3
  129. #define BYTE_SHIFT        3
  130. #define INT_TO_BYTE        2
  131. #define INT_BYTE_SHIFT        5
  132. #define ALL_SET     ((unsigned)0xFFFFFFFF)
  133. #define ALL_CLEAR        0
  134.  
  135.  
  136. #define PTROF(X)        ((BUFHEAD *)((unsigned)(X)&~0x3))
  137. #define ISMOD(X)        ((unsigned)(X)&0x1)
  138. #define DOMOD(X)        (X = (char *)( (unsigned)X | 0x1))
  139. #define ISDISK(X)       ((unsigned)(X)&0x2)
  140. #define DODISK(X)       (X = (char *)( (unsigned)X | 0x2))
  141.  
  142. #define BITS_PER_MAP    32
  143.  
  144. /* Given the address of the beginning of a big map, clear/set the nth bit */
  145.  
  146. #define CLRBIT(A,N) ((A)[N/BITS_PER_MAP] &= ~(1<<(N%BITS_PER_MAP)))
  147. #define SETBIT(A,N) ((A)[N/BITS_PER_MAP] |= (1<<(N%BITS_PER_MAP)))
  148. #define ISSET(A,N) ((A)[N/BITS_PER_MAP] & (1<<(N%BITS_PER_MAP)))
  149.  
  150. /* Overflow management */
  151. /*
  152.     Overflow page numbers are allocated per split point.
  153.     At each doubling of the table, we can allocate extra
  154.     pages.    So, an overflow page number has the top 5 bits
  155.     indicate which split point and the lower 11 bits indicate
  156.     which page at that split point is indicated (pages within
  157.     split points are numberered starting with 1).
  158.  
  159.  
  160. */
  161.  
  162. #define SPLITSHIFT    11
  163. #define SPLITMASK    0x7FF
  164. #define SPLITNUM(N)     (((unsigned)N) >> SPLITSHIFT)
  165. #define OPAGENUM(N)     (N & SPLITMASK)
  166. #define OADDR_OF(S,O)   ((unsigned)((unsigned)S << SPLITSHIFT) + O)
  167.  
  168. #define BUCKET_TO_PAGE(B) \
  169.     B + hashp->HDRPAGES + (B ? hashp->SPARES[__log2(B+1)-1] : 0)
  170. #define OADDR_TO_PAGE(B)        \
  171.     BUCKET_TO_PAGE ( (1 << SPLITNUM(B)) -1 ) + OPAGENUM(B);
  172.  
  173. /*
  174.     page.h contains a detailed description of the page format.
  175.  
  176.     Normally, keys and data are accessed from offset tables in the
  177.     top of each page which point to the beginning of the key and
  178.     data.  There are four flag values which may be stored in these
  179.     offset tables which indicate the following:
  180.  
  181.     OVFLPAGE    Rather than a key data pair, this pair contains
  182.             the address of an overflow page.  The format of
  183.             the pair is:
  184.                 OVERFLOW_PAGE_NUMBER OVFLPAGE
  185.  
  186.     PARTIAL_KEY    This must be the first key/data pair on a page
  187.             and implies that page contains only a partial key.
  188.             That is, the key is too big to fit on a single page
  189.             so it starts on this page and continues on the next.
  190.             The format of the page is:
  191.                 KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
  192.  
  193.                 KEY_OFF -- offset of the beginning of the key
  194.                 PARTIAL_KEY -- 1
  195.                 OVFL_PAGENO - page number of the next overflow page
  196.                 OVFLPAGE -- 0
  197.     FULL_KEY    This must be the first key/data pair on the page.  It
  198.             is used in two cases.
  199.  
  200.             Case 1:
  201.                 There is a complete key on the page but no data
  202.                 (because it wouldn't fit).  The next page contains
  203.                 the data.
  204.  
  205.                 Page format it:
  206.                 KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  207.  
  208.                 KEY_OFF -- offset of the beginning of the key
  209.                 FULL_KEY -- 2
  210.                 OVFL_PAGENO - page number of the next overflow page
  211.                 OVFLPAGE -- 0
  212.  
  213.             Case 2:
  214.                 This page contains no key, but part of a large
  215.                 data field, which is continued on the next page.
  216.  
  217.                 Page format it:
  218.                 DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  219.  
  220.                 KEY_OFF -- offset of the beginning of the data on
  221.                     this page
  222.                 FULL_KEY -- 2
  223.                 OVFL_PAGENO - page number of the next overflow page
  224.                 OVFLPAGE -- 0
  225.  
  226.     FULL_KEY_DATA    This must be the first key/data pair on the page.
  227.             There are two cases:
  228.  
  229.             Case 1:
  230.                 This page contains a key and the beginning of the
  231.                 data field, but the data field is continued on the
  232.                 next page.
  233.  
  234.                 Page format is:
  235.                 KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
  236.  
  237.                 KEY_OFF -- offset of the beginning of the key
  238.                 FULL_KEY_DATA -- 3
  239.                 OVFL_PAGENO - page number of the next overflow page
  240.                 DATA_OFF -- offset of the beginning of the data
  241.  
  242.             Case 2:
  243.                 This page contains the last page of a big data pair.
  244.                 There is no key, only the  tail end of the data
  245.                 on this page.
  246.  
  247.                 Page format is:
  248.                 DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
  249.  
  250.                 DATA_OFF -- offset of the beginning of the data on
  251.                     this page
  252.                 FULL_KEY_DATA -- 3
  253.                 OVFL_PAGENO - page number of the next overflow page
  254.                 OVFLPAGE -- 0
  255.  
  256.                 OVFL_PAGENO and OVFLPAGE are optional (they are
  257.                 not present if there is no next page).
  258. */
  259.  
  260. #define OVFLPAGE    0
  261. #define PARTIAL_KEY    1
  262. #define FULL_KEY    2
  263. #define FULL_KEY_DATA    3
  264. #define REAL_KEY    4
  265. /* Short hands for accessing structure */
  266. #define BSIZE    hdr.bsize
  267. #define BSHIFT    hdr.bshift
  268. #define DSIZE    hdr.dsize
  269. #define SGSIZE    hdr.ssize
  270. #define SSHIFT    hdr.sshift
  271. #define LORDER    hdr.lorder
  272. #define MAX_BUCKET    hdr.max_bucket
  273. #define FFACTOR     hdr.ffactor
  274. #define HIGH_MASK    hdr.high_mask
  275. #define LOW_MASK    hdr.low_mask
  276. #define NKEYS        hdr.nkeys
  277. #define HDRPAGES    hdr.hdrpages
  278. #define SPARES        hdr.spares
  279. #define BITMAPS     hdr.bitmaps
  280. #define VERSION     hdr.version
  281. #define MAGIC        hdr.magic
  282. #define NEXT_FREE    hdr.next_free
  283. #define H_CHARKEY    hdr.h_charkey
  284.  
  285. #endif
  286.